\section{Problem 3}

	The following parameters for a $B^{+}$-tree are used in that problem :\\

	\begin{tabular}{|l|c|r|}
	\hline
		\textbf{Description} & \textbf{Notation in formula} & \textbf{Value}\\
	\hline
		Number of records to be stored & $numberOfRecords$ & $3 \times 10^{10}$\\
	\hline
		Size of a record & $recordSize$ & 380 bytes\\
	\hline
		Size of a pointer to $B^{+}$-tree node & $pointerSize$ & 6 bytes\\
	\hline
		Size of internal $B^{+}$-tree key & $keySize$ & 30 bytes\\
	\hline
		Total size of sequential pointers $B^{+}$-tree leaves & $seqPointerSize$ & 12 bytes\\
	\hline
		Page size & $pageSize$ & 8192 bytes\\
	\hline
	\end{tabular}

\subsection*{Question a}

The number of keys which may be stored in a single internal vertex is given by the following inequation :
	\begin{equation}
		(n \times pointerSize) + ((n - 1) \times keySize) \leq pageSize
	\end{equation}
Thus: 
	\begin{displaymath}
		\begin{array}{r c l}
			n&\leq & \dfrac{pageSize + keySize}{pointerSize + keySize}\\
			n&\leq & \dfrac{8192 + 30}{6 + 30}\\
			n&\leq & 228,39
		\end{array}
	\end{displaymath}
	
Consequently 228 keys can be stored in each internal vertex.

\subsection*{Question b}

The number of records which may be stored in a leaf is computed with this formula : 
	\begin{equation}
		(r_{max} \times recordSize) + seqPointerSize \leq pageSize
	\end{equation}
Thus: 
	\begin{displaymath}
		\begin{array}{r c l}
			r_{max}&\leq & \dfrac{pageSize - seqPointerSize}{recordSize}\\
			&&\\
			r_{max}&\leq & \dfrac{8192 - 12}{380}\\
			&&\\
			r_{max}&\leq & 21,526315789
		\end{array}
	\end{displaymath}
	
A maximum of 21 records might be stored in each leaf.

\subsection*{Question c}

The lower is its the density, the greater is $B^{+}$-tree depth. Thus, in order to find the maximum depth of a $B^{+}$-tree, the number of records per leaf and the the number of keys per internal vertex must be set to their minimum.
With the previously found $r_{max}$ and $n$ parameters, these conditions are : 
		\begin{displaymath}
			\left\lbrace
			\begin{array}{r c l}
					m & = & 1\\
					q & = & \dfrac{n}{2} = 114\\
					&&\\
					r & = & \dfrac{r_{max}}{2} = 11
			\end{array}
			\right.
		\end{displaymath}
		
	where $m$ is the number of keys in the root, $q$ the number of keys the others internal nodes, and $r$ the number of records per leaf.
	
$d_{max}$ can be computed by the following equation :
	\begin{equation}
			d_{max} \leq \dfrac{ln\left(\dfrac{numberOfRecords}{(m + 1) \times r}\right)}{ln(q + 1)} + 1
			\label{eq:maxdepth+}
	\end{equation}
	
Applied to the previous conditions : 
	\begin{displaymath}
		\begin{array}{r c l}
			d_{max}&\leq & \dfrac{ln\left(\dfrac{3.10^{10}}{(1 + 1) \times 11}\right)}{ln(114 + 1)} + 1\\
			&\leq & 5,432818046
		\end{array}
	\end{displaymath}
	
Then maximum depth is $5$.

\subsection*{Question d}

The total number of records $N$ for the arguments $m$, $r$, $q$ and $d$ is given by :
	\begin{equation}
		N = (m + 1).(q + 1)^{d - 1}.r
	\end{equation}
	
With the following parameters
		\begin{displaymath}
			\left\lbrace
			\begin{array}{r c l}
					m & = & 1\\
					N & = & 3.10^{10}\\
					r & = & r_{min} = 11
			\end{array}
			\right.
		\end{displaymath}
		we can then deduce $q$.
		
	\begin{displaymath}
		\begin{array}{r c l}
		q &=& \sqrt[d - 1]{\dfrac{N}{r(m + 1)}} - 1\\
		&&\\
		q &=& \sqrt[5 - 1]{\dfrac{3.10^{10}}{11\times(1 + 1)}} - 1\\
		&&\\
		q &=& 191,165156295
		\end{array}
	\end{displaymath}
	which respects the condition of q $\geq$ 114.
	
\subsection*{Question e}

Contrary to the maximum depth, the minimal depth is found when both leaves and vertices are as full as possible. Thus, each vertex, including root is attempted to store 228 keys, and each leaf, 21 records.

$d_{min}$ is given by the same following formula \ref{eq:maxdepth+}.
	
Applied to the conditions : 
	\begin{displaymath}
		\begin{array}{r c l}
			d_{min}&\geq & \dfrac{ln\left(\dfrac{3.10^{10}}{(228 + 1) \times 21}\right)}{ln(228 + 1)} + 1\\
			&\geq & 3,879466187
		\end{array}
	\end{displaymath}

The minimal depth of this $B^{+}$-tree is $4$.

\subsection*{Question f}

As in 3.d, $q$ may be found by the following formula :
	\begin{equation}
		N = (m + 1).(q + 1)^{d - 1}.r
	\end{equation}

Since $m$ is set to be equal to $q$, this last one is given by the formula : 
	\begin{equation}
		\begin{array}{r c l}
			N &=& (q + 1).(q + 1)^{d - 1}.r\\
			N &=& (q + 1)^{d}.r\\
			q &=& \sqrt[d]{\dfrac{N}{r}} - 1\\
		\end{array}
	\end{equation}
	
Thus, with the following parameters, 
		\begin{displaymath}
			\left\lbrace
			\begin{array}{r c l}
					N & = & 3.10^{10}\\
					r & = & r_{max} = 21\\
					d & = & d_{min} = 4
			\end{array}
			\right.
		\end{displaymath}
	we find :
\begin{displaymath}
		\begin{array}{r c l}
			q &=& \sqrt[4]{\dfrac{3.10^{10}}{21}} - 1\\
			&&\\
			q &=& 193,413084181
		\end{array}
\end{displaymath}
	which respects the condition of q $\leq$ 228.
	
\section*{Question g}

With the given parameters, one and only one vertex is stored per page. Thus, the number of vertices which can be stored in 8 gigabytes is the number of pages which can be contained by the memory space :
			\begin{displaymath}
				\dfrac{memorySpace}{pageSize} = \dfrac{2^{33}}{8192} = 1048576
			\end{displaymath}